Depressed individuals are at increased risk for numerous physical health problems. More physical activity decreases risk of physical health problems, and physical activity may also reduce depression symptoms. However, relative to non-depressed people, depressed individuals have low rates of physical activity and poor adherence to exercise interventions. This is likely due, at least in part, to specific core features of depression, including anhedonia (lackof interest or pleasure), amotivation, fatigue, and poorer problem-solving abilities. Previous research on physical activity in depressed groups has focused primarily on whether physical activity is an efficacious depression treatment. However, virtually no research has addressed key questions about optimal strategies for increasing and maintaining physical activity among depressed individuals. Remaining questions include: 1) Can a psychological intervention that specifically targets depression-related exercise barriers combined with an exercise program increase and maintain physical activity more effectively than an exercise program alone?; and 2) Can exercise programs not only increase physical activity during the active intervention phase, but also lead to sustained increased activity in a follow-up phase? We propose a randomized clinical trial in which 240 depressed individuals are assigned to one of three arms, with each successive arm having an added component that may serve to increase and maintain physical activity: 1) brief advice (BA) to exercise (control condition); 2) BA + supervised & home-based exercise (SHE); and 3) BA+SHE+ a cognitive-behavioral program focused on increasing and maintaining exercise (CBEX). BA will consist of one 45-minute session about benefits of physical activity and public health recommendations. SHE will be a 3-month intervention consisting of 1x/week supervised exercise plus exercise prescriptions for home- based exercise with the goal of gradually achieving the public health recommendation of 150 minutes/ week of moderate-to-vigorous physical activity (MVPA). In the BA+SHE+CBEX intervention, weekly 30-minute CBEX sessions will be added in order to address barriers to physical activity that are particularly pronounced in depression. The primary aims are: to compare the efficacy of the 3 arms for increasing physical activity at the end of the 3-month intervention phase, and to compare the long-term impact of the three arms on objectively- measured minutes of MVPA at 6- and 9-month follow-ups. We hypothesize that BA + SHE + CBEX will be superior to BA + SHE, and that BA + SHE will be superior to BA alone in terms of MVPA levels. Secondary aims include assessing the impact of interventions on depression as well as physical health outcomes including cardiorespiratory fitness and body composition; determining whether amount of MVPA mediates the association between group assignment and change in depressive symptoms; and examining behavior change theory-based mediators of the association between group assignment and amount of MVPA.